//编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。 
//
// 注意：本题相对原题稍作修改 
//
// 示例： 
//
// 
//输入：["eat", "tea", "tan", "ate", "nat", "bat"],
//输出：
//[
//  ["ate","eat","tea"],
//  ["nat","tan"],
//  ["bat"]
//] 
//
// 说明： 
//
// 
// 所有输入均为小写字母。 
// 不考虑答案输出的顺序。 
// 
//
// Related Topics 数组 哈希表 字符串 排序 👍 117 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-09-01 22:40:32
 * @description 面试题 10.02.变位词组
 */
public class GroupAnagramsLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 GroupAnagramsLcci fun=new GroupAnagramsLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public List<List<String>> groupAnagrams1(String[] ss) {
		List<List<String>> ans = new ArrayList<>();
		Map<String, List<String>> map = new HashMap<>();
		for (String s : ss) {
			char[] cs = s.toCharArray();
			Arrays.sort(cs);
			String key = String.valueOf(cs);
			List<String> list = map.getOrDefault(key, new ArrayList<>());
			list.add(s);
			map.put(key, list);
		}
		for (String key : map.keySet()) ans.add(map.get(key));
		return ans;
	}

	public List<List<String>> groupAnagrams2(String[] ss) {
		List<List<String>> ans = new ArrayList<>();
		Map<String, List<String>> map = new HashMap<>();
		for (String s : ss) {
			int[] cnts = new int[26];
			for (char c : s.toCharArray()) cnts[c - 'a']++;
			StringBuilder sb = new StringBuilder();
			for (int i : cnts) sb.append(i + "_");
			String key = sb.toString();
			List<String> list = map.getOrDefault(key, new ArrayList<>());
			list.add(s);
			map.put(key, list);
		}
		for (String key : map.keySet()) ans.add(map.get(key));
		return ans;
	}



	//相当于给每个字母都定义了一个质数表示，然后计算每个字符的hashcode（乘积）但是 会可能溢出，如果取mod可能has冲突
	public List<List<String>> groupAnagrams(String[] ss) {
		 int[] nums = new int[26];

			for (int i = 2, idx = 0; idx != 26; i++) {
				boolean ok = true;
				for (int j = 2; j <= i / j; j++) {
					if (i % j == 0) {
						ok = false;
						break;
					}
				}
				if (ok) nums[idx++] = i;
			}

		List<List<String>> ans = new ArrayList<>();
		Map<Long, List<String>> map = new HashMap<>();
		for (String s : ss) {
			long cur = 1;
			for (char c : s.toCharArray()) {
				cur *= nums[c - 'a'];
			}
			List<String> list = map.getOrDefault(cur, new ArrayList<>());
			list.add(s);
			map.put(cur, list);
		}
		for (long key : map.keySet()) ans.add(map.get(key));
		return ans;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
